package leet.ku._234;

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

public class Solution {
	public boolean isPalindrome(ListNode head) {
		if (head == null)
			return true;
		
		int count = 0;
		ListNode p = head;
		while (p != null) {
			count++;
			p = p.next;
		}
		p = head;
		for (int i = 0; i < count / 2; i++, p = p.next);
		
		ListNode q = null;
		while (p != null) {
			ListNode r = new ListNode(p.val);
			r.next = q;
			q = r;
			p = p.next;
		}
		
		while (q != null) {
			if (head.val != q.val)
				return false;
			head = head.next;
			q = q.next;
		}
		return true;
	}
}